class Solution(object):
    def atMostNGivenDigitSet(self, digits, n):
        n_str = str(n)
        m = len(n_str)
        t = len(digits)
        self.ans = 0
        for q in range(1, m):
            self.ans += t ** q


        def dfs(i):
            if i < m:
                base = None
                q = 0
                for c in digits:
                    if c < n_str[i]:
                        q += 1
                    if c == n_str[i]:
                        base = c
                        break
                self.ans += q * t ** (m - 1 - i)
                if base:
                    dfs(i + 1)
            else:
                self.ans += 1

        dfs(0)
        return self.ans



data = Solution()
digits = ["1", "3", "5", "7"]
n = 100
print(data.atMostNGivenDigitSet(digits, n))
digits = ["1","4","9"]
n = 1000000000
print(data.atMostNGivenDigitSet(digits, n))
digits = ["7"]
n = 8
print(data.atMostNGivenDigitSet(digits, n))